package com.atcumt.CodeTop;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

/*
 * 1、三数之和
 * 2、最大子序和
 * 3、k个一组反转链表
 * 4、合并有序链表
 * 5、环形链表
 * 6、搜索旋转排序数组
 */
public class day01 {

    /*
     * 1.三数之和 排序 + 双指针, 收缩双指针注意去重
     * 输入：nums = [-1,0,1,2,-1,-4]
     * 输出：[[-1,-1,2],[-1,0,1]]
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length < 3) {
            return res;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 去重
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return res;
    }

    /*
     * 最大子序和
     * f[i]为前i个元素，且包括第 nums[i]，子数组的最大和
     */
    public int maxSubArray(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        int res = nums[0]; // 初始化
        for (int i = 0; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    /*
     * k个一组反转链表 栈
     * 输入：head = [1,2,3,4,5], k = 3
     * 输出：[3,2,1,4,5]
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        Deque<ListNode> stack = new ArrayDeque<>();
        ListNode dummy = new ListNode(-1);
        ListNode pre = dummy;
        while (true) {
            int count = 0;
            ListNode cur = head; // 临时节点

            while (cur != null && count < k) {
                stack.push(cur);
                cur = cur.next;
                count++;
            }
            // 不够 k个不用翻转
            if (count != k) {
                pre.next = head;
                break;
            }
            while (!stack.isEmpty()) {
                pre.next = stack.pop();
                pre = pre.next;
            }
            // 反转后的部分与剩下的部分相接
            pre.next = cur;
            head = cur;
        }
        return dummy.next;
    }

    /*
     * 合并两个有序链表：递归，每次递归比较两个链表当前节点的大小
     * 判断每次的list1和list2的头结点大小，将较小结点的next指针指向其余的待递归的结点合并结果
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null || list2 == null) {
            return list1 == null ? list2 : list1;
        }

        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }

    /*
     * 环形链表：双指针
     * 如果不含有环，跑得快的那个指针最终会遇到 null，说明链表不含环；
     * 如果含有环，快指针最终会超慢指针一圈，和慢指针相遇，说明链表含有环
     */
    public boolean hasCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    /**
     * 环形链表Ⅱ
     * 找到相遇点。快慢指针一直走，直到快慢指针相等。循环条件是快指针和其Next不为空
     * 新指针从头部出发，循环条件是新指针不等于慢指针，跳出循环，直接返回新指针
     * 如果是非环链表的话，快指针早就为空，不会进入第二步
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast =fast.next.next;
            slow = slow.next.next;
            if (fast == slow) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            // fast遇到空指针说明没环
            return null;
        }
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;

    }

    /*
     * 搜索旋转数组：二分查找
     * 二分的本质是两段性，并非单调性。只要一段满足有序性，另一段不满足某个性质，就可以使用二分
     * 输入：nums = [4,5,6,7,0,1,2], target = 0
     * 输出：4
     */
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (target == nums[mid]) {
                return mid;
            }

            if (nums[mid] >= nums[left]) {
                if (target < nums[mid] && target >= nums[left]) {
                    right = mid - 1; // target 刚好在左侧
                } else {
                    left = mid + 1;
                }
            } else {
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1; // target 刚好在右侧
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}
